#ifndef _LIST_H_
#define _LIST_H_

#include "pagemempool.h"

#pragma once

template< class T > class List;
template< class T > class List_Iterator;
template< class T > class List_Node;

template< class T >
class List_Node
{
public:
	typedef List_Node<T>	base_type;

	List_Node( T * item )
		: m_item( item ),
	      m_prev( NULL ),
	      m_next( NULL )
	{}

	T * get_item() const { return m_item; }

	base_type * get_prev() const { return m_prev; }
	void set_prev( base_type * prev ) { m_prev = prev; }

	base_type * get_next() const { return m_next; }
	void set_next( base_type * next ) { m_next = next; }

private:
	T*	m_item;
	base_type * m_prev;
	base_type * m_next;
};

template< class T >
class List_Iterator
{
public:
	typedef List_Node<T>	node_type;
	friend class List<T>;

	List_Iterator()
		: m_course( NULL )
	{}

    List_Iterator( const List_Iterator & iter )
        : m_course( iter.m_course )
    {}

	List_Iterator( node_type * head )
		: m_course( head )
	{}

	List_Iterator & operator= ( const List_Iterator & iter )
	{
		m_course = iter.m_course;
		return *this;
	}

	bool is_done() const {
		return NULL == m_course;
	}

	T * value() const {
		if( NULL != m_course )
			return m_course->get_item();
		return NULL;
	}

	void next() const {
		if( NULL != m_course )
			m_course = m_course->get_next();
	}

private:
	mutable node_type * m_course;
};

template< class T >
class List
{
public:
	typedef List<T> 				base_type;
	typedef List_Node<T>			node_type;
	typedef List_Iterator<T>		iterator;
	typedef PageMemPool<node_type>	alloc_node_type;

	List()
		: m_head( NULL ),
	      m_tail( NULL ),
	      m_size( 0 )
	{}

	~List() throw()
	{
		clean();
	}

    List( const List & other )
        : m_head( NULL ),
	      m_tail( NULL ),
	      m_size( 0 )
    {
        if( 0 != other.m_size )
        {
        	iterator iter = other.get_iterator();
        	while( !iter.is_done() )
        	{
        		push_back( iter.value() );
                iter.next();
        	}
        }
    }

    List & operator= ( const List & other )
    {
        clean();
        if( 0 != other.m_size )
        {
        	iterator iter = other.get_iterator();
        	while( !iter.is_done() )
        	{
        		push_back( iter.value() );
                iter.next();
        	}
        }
    }

	T * begin() const
	{
		if( NULL != m_head )
			return m_head->get_item();
		return NULL;
	}

	T * end() const
	{
		if( NULL != m_head )
			return m_tail->get_item();
		return NULL;
	}

    int32_t insert( iterator iter, T * item )
    {
		node_type * node = alloc_node( item );
		if( NULL == node )
			return -1;

        node_type * sub_node = iter.m_course;
        if( NULL == m_head )
        {
            m_head = m_tail = node;
        }
        else if( m_head == sub_node )
        {
            m_head = node;
            node->set_next( sub_node );
            sub_node->set_prev( node );
        }
        else if( m_tail == sub_node )
        {
            m_tail = node;
            node->set_prev( sub_node );
            sub_node->set_next( node );
        }
        else
        {
            node->set_prev( sub_node->get_prev() );
            node->set_next( sub_node );
            sub_node->get_prev()->set_next( node );
            sub_node->set_prev( node );
        }
        ++m_size;
        return 0;
    }

	int32_t push_back( T * item )
	{
		node_type * node = alloc_node( item );
		if( NULL == node )
			return -1;

		node->set_next( NULL );
		node->set_prev( m_tail );

		if( NULL != m_tail )
			m_tail->set_next( node );

		m_tail = node;

		if( NULL == m_head )
			m_head = node;

		++m_size;
		return 0;
	}

	int32_t push_front( T * item )
	{
		node_type * node = alloc_node( item );
		if( NULL == node )
			return -1;

		node->set_next( m_head );
		node->set_prev( NULL );

		if( NULL != m_head )
			m_head->set_prev( node );

		m_head = node;

		if( NULL == m_tail )
			m_tail = node;

		++m_size;
		return 0;
	}

	T * pop_head()
	{
		if( NULL == m_head )
			return NULL;

		node_type * node = m_head;
		T * item = node->get_item();

		if( m_head == m_tail )
			m_head = m_tail = NULL;
		else
		{
			m_head = m_head->get_next();
			m_head->set_prev( NULL );
		}
		release_node( node );
		--m_size;
		return item;
	}

	T * pop_tail()
	{
		if( NULL == m_tail )
			return NULL;

		node_type * node = m_tail;
		T * item = node->get_item();

		if( m_head == m_tail )
			m_head = m_tail = NULL;
		else
		{
			m_tail = m_tail->get_prev();
			m_tail->set_next( NULL );
		}
		release_node( node );
		--m_size;
		return item;
	}

	iterator get_iterator() const
	{
		return iterator( m_head );
	}

    iterator get_end_iterator() const
    {
        return iterator( m_tail );
    }

	T * erase( iterator & iter )
	{
		node_type * node = iter.m_course;
		if( NULL == node )
			return NULL;

		iter.m_course = iter.m_course->get_next();

		T * temp = node->get_item();

		if( node == m_head )
			m_head = m_head->get_next();
		if( node == m_tail )
			m_tail = m_tail->get_prev();

		if( NULL != node->get_prev() )
			node->get_prev()->set_next( node->get_next() );

		if( NULL != node->get_next() )
			node->get_next()->set_prev( node->get_prev() );

		release_node( node );
		--m_size;
		return temp;
	}

	uint32_t size() const
	{
		return m_size;
	}

private:
	node_type * alloc_node( T * item )
	{
		node_type * node = new node_type( item ); //m_allocator.alloc( __FILE__, __LINE__ );
		if( NULL == node )
			return NULL;
		return node;
	}

	void release_node( node_type * node )
	{
		if( NULL == node )
			return;
		//node->~List_Node<T>();
		//m_allocator.release( node, __FILE__, __LINE__ );
		delete node;
	}

    void clean()
    {
		node_type * node = m_head;
		while( node )
		{
			node_type * del_node = node;
			node = node->get_next();
			release_node( del_node );
		}
		m_head = m_tail = NULL;
		m_size = 0;
    }

private:
	node_type *		m_head;
	node_type *		m_tail;
	uint32_t		m_size;
//	alloc_node_type	m_allocator;
};


#endif // _LIST_H_
